In [ ]:

    

<b>Problem 5</b>

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?


    

In [1]:

    

from fractions import gcd


    

In [10]:

    

least_common_multiple = 1
for i in range(1,20):
    greatest_divisor = gcd(least_common_multiple,i+1)
    least_common_multiple = least_common_multiple*(i+1)/greatest_divisor
print (least_common_multiple)


    

    




232792560.0

In [11]:

    

from math import sqrt


    

In [30]:

    

def find_n_primes(number_of_primes):
    "This function returns a list of all containing the first n primes"
    i = 2
    primelist = []
    while(len(primelist) < number_of_primes):
        marker = "Prime"
        for j in range(2,int(sqrt(i))+1):
                   if( i%j == 0):
                       marker ="No"
                       break
                        
        if (marker == "Prime" ):
            primelist.append(i)
            #print(i)
        i +=1
    return(primelist)


    

In [35]:

    

list = find_n_primes(10001)
list[-1]


    

    
Out[35]:





104743

In [8]:

    

number_as_string = str(731671765313306249192251196\
74426574742355349194934969835203127745063262395783\
1801698480186947885184385861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450)


    

In [29]:

    

max_product = 0
for i in range(len(number_as_string)-13):
    product = 1
    for j in range(13):
        product *= int(number_as_string[i+j])
    if (product > max_product):
        max_product = product
        adjacent_digits = number_as_string[i:i+13]


    

In [32]:

    

print(max_product, adjacent_digits)


    

    




23514624000 5576689664895

In [37]:

    

for a in range(1,1000):
    for b in range(a+1,1000):
        c = 1000 - a - b
        if (a**2 + b**2 == c**2):
            print(a , b, c)


    

    




200 375 425

In [14]:

    

from math import sqrt
def primesum_upto(max_number):
    "This function returns a list of primes upto the input value which is assumed to be positive"
    i = 2
    sum_of_primes = 0
    while(i < max_number):
        marker = "Prime"
        for j in range(2,int(sqrt(i))+1):
                   if( i%j == 0):
                       marker ="No"
                       break
                        
        if (marker == "Prime" ):
            sum_of_primes += i
        i +=1
    return(sum_of_primes)


    

In [16]:

    

primesum_upto(2*10**6)


    

    
Out[16]:





142913828922

In [47]:

    

from math import sqrt

def triangle_number(n):
    "returns the nth triangle number"
    return(int(n*(n+1)/2))

def factorlist(n):
    "Returns a list of all the divisors of the given value n"
    factorslist = [1, n]
    for i in range(2,int(sqrt(n))+1):
        if (n%i == 0):
            factorslist.append(i)
            if( i  != int(n/i)):
                factorslist.append(int(n/i))
    return(factorslist)


    

In [70]:

    

number_of_divisors = 0
n = 0
while(number_of_divisors < 500):
    n += 1
    number_of_divisors = len(factorlist(triangle_number(n)))
    #print("\nn = ",n,"\tTriangle Number = ", triangle_number(n),"\tNumber of divisors =", number_of_divisors)
    
print("\nn = ",n,"\tTriangle Number = ", triangle_number(n),"\tNumber of divisors =", number_of_divisors)


    

    




n =  12375 	Triangle Number =  76576500 	Number of divisors = 576

In [88]:

    

#The above list of numbers should be copied and pasted into a file called project_euler_problem13.txt
filehandle = open("project_euler_problem13.txt","r")
sum_of_values = 0
for line in filehandle:
    sum_of_values += int(line)
print("The total sume is",sum_of_values)    
print("The first ten digits are",(str(sum_of_values))[0:10])


    

    




The total sume is 5537376230390876637302048746832985971773659831892672
The first ten digits are 5537376230

In [1]:

    

def next_term_in_collatz_chain( n ):
    #Returns n/2 (if n even) or 3n+1 otherwise
    if(n%2 == 0):
        return(int(n/2))
    elif( n == 1):
            return(1)        
    else:
        return(3*n+1)


    

    




2

In [49]:

    

#Slowest of all solutions
max_iterations = 10**6
max_chain_length = 0
max_chain_start_term = 1

for i in range(1,max_iterations):
    chain = []
    term_value = i
    while(term_value > 1):
        term_value = next_term_in_collatz_chain(term_value)
        chain.append(term_value)
    if(len(chain) > max_chain_length):
        max_chain_length = len(chain)
        max_chain_start_term = i
    
print("The max chain length is", max_chain_length,"with start term",max_chain_start_term)


    

    




The max chain length is 524 with start term 837799

In [53]:

    

#Optimised 1
#This code should run a lot faster than the one above because redundant chains not generated
#i.e. if a value appears WITHIN chain then this value itself cannot be the start of the longest chain.
#The max chain length is 524 with start term 837799

max_iterations = 10**6
max_chain_length = 0
max_chain_start_term = 1

a = [1]*max_iterations #Filter list, this will keep a record of which chains have already been seen

for i in range(1,max_iterations):
    if (a[i] == 1):
        chain = []
        term_value = i
        while(term_value > 1):
            term_value = next_term_in_collatz_chain(term_value)
            if(term_value < len(a)):
                a[term_value] = 0
            chain.append(term_value)
        if(len(chain) > max_chain_length):
            max_chain_length = len(chain)
            max_chain_start_term = i
        
    
print("The max chain length is", max_chain_length,"with start term",max_chain_start_term)


    

    




The max chain length is 524 with start term 837799

In [3]:

    

from math import factorial
routes  = int(factorial(40)/factorial(20)**2)
print("The number of routes on a 20x20 grid is",routes)


    

    




The number of routes on a 20x20 grid is 137846528820

In [10]:

    

#Here we generate all the different possible paths for fun
#An outcome tree similar to a probabilty tree will be used
#del list[:] and list[:]=[] will be used to conserve memory
#list.pop() could also have been used

def right_node_creator(old_node, new_nodes):
    #This creates a node element with one move to the right
    return(new_nodes.append([old_node[0]+'R',old_node[1]-1,old_node[2]]))

def down_node_creator(old_node, new_nodes):
    #This creates a node element with one move to the right
    return(new_nodes.append([old_node[0]+'D',old_node[1],old_node[2]-1]))

old_nodes = [['',20,20]]
for move_number in range(1,10):
    new_nodes = []
    for i in old_nodes:
        if(i[1] > 0): #Right node creation test
            right_node_creator( i , new_nodes )
        if(i[2] > 0): #Down node creation test
            down_node_creator( i , new_nodes )
    del old_nodes[:]
    old_nodes = new_nodes


    

In [17]:

    

%reset out


    

    




Once deleted, variables cannot be recovered. Proceed (y/[n])? y
Flushing output cache (0 entries)

In [2]:

    

import numpy as np
from math import factorial
routes  = int(factorial(40)/factorial(20)**2)


    

In [20]:

    

#Using Numpy arrays
#Here we generate all the different possible paths for fun
#An outcome tree similar to a probabilty tree will be used
#Numpy arrays are contiginous memmory allocation therefore 
#inplace append and insert does not exist. Memory allocation needs
#to be declared at start for maximum efficiency. ... Great(!)...

#def right_node_creator(nodes):
    #This creates a node element with one move to the right
 #   return(np.array([old_node[0]+'R',int(old_node[1])-1,old_node[2]]))

#def down_node_creator(nodes):
    #This creates a node element with one move to the right
 #   return(np.array([old_node[0]+'D',old_node[1],int(old_node[2])-1]))

nodes = np.array([0]*(100000000))
100000000
137846528820
#nodes[1] = ['',20,20]
j = 1 #This will keep track of the next unused memory slot in the Numpy array

#for move_number in range(1,2):
#    new_nodes = np.array([])
#    for i in old_nodes:
#        if(int(i[1]) > 0): #Right node creation test
#            a = right_node_creator( i )
#            np.append(new_nodes,a,axis=0)
#        if(int(i[2]) > 0): #Down node creation test
#            a = down_node_creator( i )
#            np.append(new_nodes,a,axis=0)
#    print(old_nodes)
    #print(new_nodes)
    #old_nodes = new_nodes
#type(a)


    

In [21]:

    

nodes.nbytes


    

    
Out[21]:





800000000

In [42]:

    

from math import factorial


    

In [69]:

    

#The approach below is WRONG due to the trailing zeros on the end of 100!
n = factorial(100)
sum_digits = 0
while ( n ):
    sum_digits += (n % 10)
    n = int( n/10 )
print (sum_digits)


    

    




675

In [70]:

    

#This approach yields the correct answer!
n_string = str(factorial(100))
sum_digits = 0
for i in n_string:
    sum_digits += int(i)
print (sum_digits)


    

    




648